Search for: All records

We present a proof under a generalization of the Riemann Hypothesis that the class group algorithm of Hafner and McCurley runs in expected time \begin{document}$$ e^{\left(3/\sqrt{8}+o(1)\right)\sqrt{\log d\log\log d}} $$\end{document} where \begin{document}$ -d $$\end{document} is the discriminant of the input imaginary quadratic order. In the original paper, an expected run time of \begin{document}$$ e^{\left(\sqrt{2}+o(1)\right)\sqrt{\log d\log\log d}} $$\end{document}$ was proven, and better bounds were conjectured. To achieve a proven result, we rely on a mild modification of the original algorithm, and on recent results on the properties of the Cayley graph of the ideal class group. 

Abstract In this paper we provide a framework for applying classical search and preprocessing to quantum oracles for use with Grover’s quantum search algorithm in order to lower the quantum circuit-complexity of Grover’s algorithm for single-target search problems. This has the effect (for certain problems) of reducing a portion of the polynomial overhead contributed by the implementation cost of quantum oracles and can be used to provide either strict improvements or advantageous trade-offs in circuit-complexity. Our results indicate that it is possible for quantum oracles for certain single-target preimage search problems to reduce the quantum circuit-size from O 2 n / 2 ⋅ m C $$O\left(2^{n/2}\cdot mC\right)$$ (where C originates from the cost of implementing the quantum oracle) to O ( 2 n / 2 ⋅ m C ) $$O(2^{n/2} \cdot m\sqrt{C})$$ without the use of quantum ram, whilst also slightly reducing the number of required qubits. This framework captures a previous optimisation of Grover’s algorithm using preprocessing [21] applied to cryptanalysis, providing new asymptotic analysis. We additionally provide insights and asymptotic improvements on recent cryptanalysis [16] of SIKE [14] via Grover’s algorithm, demonstrating that the speedup applies to this attack and impacting upon quantum security estimates [16] incorporated into the SIKE specification [14].